# LeetCode 1248、统计「优美子数组」

# 一、题目描述

给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中 「优美子数组」 的数目。

示例 1：

输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

示例 2：

输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。

示例 3：

输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16

提示：

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length

# 二、题目解析

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 统计「优美子数组」（LeetCode 1248）：https://leetcode.cn/problems/count-number-of-nice-subarrays/
class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        // [1,1,0,1,1]
        // 统计和为 K 的子数组的数量
        int count = 0;
        
        // 记录遍历到索引为 i 的这个元素时，前缀和的值是多少
        int pre = 0;

        // 利用哈希表，以前缀和为键，出现次数为对应的值，记录 pre[i] 出现的次数 
        HashMap <Integer,Integer> mp = new HashMap <>();
        
        // 一开始，需要设置前缀和为 0 时，出现的次数为 1 次
        // 这一行的作用就是为了应对 nums[0] +nums[1] + ... + nums[i] == k 这种情况
        // 如数组 [1, 2, 3, 6]
        // 这个数组的累加和数组为 [1, 3, 【6】, 12] 
        // 如果 k = 6, 假如 mp 中没有预先存储(0, 1) 
        // 那么来到累加和为 6 的位置时，这时 mp 中存储的就只有两个数据 (1, 1), (3, 1)
        // 想去判断 mp.containsKey(pre - k) , 这时 pre - k = 6 - 6 = 0
        // 但 map 中没有 (0, 1) ，
        // 因为这个时候忽略了从下标 0 累加到下标 i 等于 k 的情况
        // 仅仅是统计了从下标大于 0 到某个位置等于 k 的所有答案
        mp.put(0, 1);

        // 开始从头到尾遍历 nums 数组，在遍历过程中，会执行两个操作
        // 1、存储索引为 i 的这个元素时，前缀和的值是多少，并且把这个值出现的频次存储到 mp 中
        // 2、判断之前有没有存储 pre - k 这种前缀和，如果有，说明 pre - k 到 pre 直接的那些元素值之和就是 k
        for (int i = 0; i < nums.length; i++) {
            
            // [1,3,2,3,5]
            // 奇数看成 1 ，偶数看成 0
            // 可以看成是下面这个数组
            // [1,1,0,1,1]
            // 存储索引为 i 的这个元素是 nums[i]
            // nums[i] 要么是 0 ，要么是 1
            // & 表示按位于操作
            // a & b 两个位都为1时，结果才为1
            // nums[i] = 1，nums[i] & 1  = 1，也就是原数组位置为奇数时，nums[i] & 1 的结果是 1
            // nums[i] = 0，nums[i] & 1  = 0，也就是原数组位置为偶数时，nums[i] & 1 的结果是 0
            // pre 是统计奇数的和
            // 存储索引为 i 的这个元素时，前缀和的值是多少
            pre += nums[i] & 1;

            // 判断之前有没有存储 pre - k 这种前缀和
            if (mp.containsKey(pre - k)) {

                // 如果有，说明 pre - k 到 pre 直接的那些元素值之和就是 k
                // 找到了一组，累加到 count 上
                count += mp.get(pre - k);

            }

            // 这个值出现的频次存储到 mp 中
            // getOrDefault：当 Map 集合中有这个 key 时，就使用这个 key 对应的 value 值
            // 如果没有就使用默认值 defaultValue
            mp.put(pre, mp.getOrDefault(pre, 0) + 1);
        }

        // 返回结果
        return count;
    }
    
}

# 2、C++ 代码

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        // 统计和为 K 的子数组的数量
        int count = 0;
        
        // 记录遍历到索引为 i 的这个元素时，前缀和的值是多少
        int pre = 0;

        // 利用哈希表，以前缀和为键，出现次数为对应的值，记录 pre[i] 出现的次数 
        unordered_map<int, int> mp;
        
        // 一开始，需要设置前缀和为 0 时，出现的次数为 1 次
        // 这一行的作用就是为了应对 nums[0] +nums[1] + ... + nums[i] == k 这种情况
        // 如数组 [1, 2, 3, 6]
        // 这个数组的累加和数组为 [1, 3, 【6】, 12] 
        // 如果 k = 6, 假如 mp 中没有预先存储(0, 1) 
        // 那么来到累加和为 6 的位置时，这时 mp 中存储的就只有两个数据 (1, 1), (3, 1)
        // 想去判断 mp.containsKey(pre - k) , 这时 pre - k = 6 - 6 = 0
        // 但 map 中没有 (0, 1) ，
        // 因为这个时候忽略了从下标 0 累加到下标 i 等于 k 的情况
        // 仅仅是统计了从下标大于 0 到某个位置等于 k 的所有答案
        mp[0] =  1;

        // 开始从头到尾遍历 nums 数组，在遍历过程中，会执行两个操作
        // 1、存储索引为 i 的这个元素时，前缀和的值是多少，并且把这个值出现的频次存储到 mp 中
        // 2、判断之前有没有存储 pre - k 这种前缀和，如果有，说明 pre - k 到 pre 直接的那些元素值之和就是 k
        for (int i = 0; i < nums.size(); i++) {

            // 存储索引为 i 的这个元素时，前缀和的值是多少
            pre += nums[i] & 1;

            // 判断之前有没有存储 pre - k 这种前缀和
            if (mp.find(pre - k) != mp.end()) {

                // 如果有，说明 pre - k 到 pre 直接的那些元素值之和就是 k
                // 找到了一组，累加到 count 上
                count += mp[pre - k];

            }

            // 这个值出现的频次存储到 mp 中
            mp[pre]++;
        }

        // 返回结果
        return count;
    }
};

# 3、Python 代码

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        # 统计和为 K 的子数组的数量
        count = 0
        
        # 记录遍历到索引为 i 的这个元素时，前缀和的值是多少
        pre = 0

        # 利用哈希表，以前缀和为键，出现次数为对应的值，记录 pre[i] 出现的次数 
        mp = collections.defaultdict(int)

        # 一开始，需要设置前缀和为 0 时，出现的次数为 1 次
        # 这一行的作用就是为了应对 nums[0] +nums[1] + ... + nums[i] == k 这种情况
        # 如数组 [1, 2, 3, 6]
        # 这个数组的累加和数组为 [1, 3, 【6】, 12] 
        # 如果 k = 6, 假如 mp 中没有预先存储(0, 1) 
        # 那么来到累加和为 6 的位置时，这时 mp 中存储的就只有两个数据 (1, 1), (3, 1)
        # 想去判断 mp.containsKey(pre - k) , 这时 pre - k = 6 - 6 = 0
        # 但 map 中没有 (0, 1) ，
        # 因为这个时候忽略了从下标 0 累加到下标 i 等于 k 的情况
        # 仅仅是统计了从下标大于 0 到某个位置等于 k 的所有答案
        mp[0] =  1

        # 开始从头到尾遍历 nums 数组，在遍历过程中，会执行两个操作
        # 1、存储索引为 i 的这个元素时，前缀和的值是多少，并且把这个值出现的频次存储到 mp 中
        # 2、判断之前有没有存储 pre - k 这种前缀和，如果有，说明 pre - k 到 pre 直接的那些元素值之和就是 k
        for i in range(len(nums)) : 

            # 存储索引为 i 的这个元素时，前缀和的值是多少
            pre += nums[i] & 1

            # 判断之前有没有存储 pre - k 这种前缀和
            # 如果有，说明 pre - k 到 pre 直接的那些元素值之和就是 k
            # 找到了一组，累加到 count 上
            # 利用 defaultdict 的特性，当 presum - k 不存在时，返回的是 0
            count += mp[pre - k]
            
            # 这个值出现的频次存储到 mp 中
            # getOrDefault：当 Map 集合中有这个 key 时，就使用这个 key 对应的 value 值
            # 如果没有就使用默认值 defaultValue
            mp[pre] += 1

        # 返回结果
        return count

← LeetCode 724、寻找数组的中心下标 LeetCode 560、和为 K 的子数组 →

# LeetCode 1248、统计「优美子数组」

# 一、题目描述

# 二、题目解析

# 三、参考代码

# 1、Java 代码

# **2、**C++ 代码

# 3、Python 代码

# 2、C++ 代码